import collections
from typing import List


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        connect = collections.defaultdict(set)
        size = len(graph)

        for n in initial:
            connect[n].add(n)
            queue = collections.deque([n])
            while queue:
                i = queue.popleft()
                for j in range(size):
                    if graph[i][j] == 1:
                        if j not in connect[n]:
                            queue.append(j)
                            connect[n].add(j)

        count = collections.Counter()

        for n in initial:
            for i in connect[n]:
                count[i] += 1

        min_idx, min_val = -1, len(graph) + 1
        for n in initial:
            num = 0
            for i in range(size):
                if count[i] > 1 or (count[i] == 1 and i not in connect[n]):
                    num += 1
            if num < min_val or (num == min_val and n < min_idx):
                min_idx, min_val = n, num

        return min_idx


if __name__ == "__main__":
    print(Solution().minMalwareSpread(graph=[[1, 1, 0], [1, 1, 0], [0, 0, 1]], initial=[0, 1]))  # 0
    print(Solution().minMalwareSpread(graph=[[1, 0, 0], [0, 1, 0], [0, 0, 1]], initial=[0, 2]))  # 0
    print(Solution().minMalwareSpread(graph=[[1, 1, 1], [1, 1, 1], [1, 1, 1]], initial=[1, 2]))  # 1

    # 测试用例55/66 : 3
    print(Solution().minMalwareSpread(graph=[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]], initial=[3, 1]))
